Search assistance modules in typical commercial search engines can be categorized into presubmit search assistance and post-submit search assistance. Presubmit search assistance is the assistance before a user submits their query, and postsubmit search assistance is the assistance provided after a user submits their query. In presubmit assistance, it is not known whether the user has finished typing his or her query, and the input, by default, is considered as a portion of a search query (also referred to herein as a prefix). On the other hand, in postsubmit assistance, the full query is known. Therefore, in general, for the same user input, the suggestions in presubmit and postsubmit can be very different. For example, consider the prefix “awk”, where the top presubmit suggestions can be “awkward”, “awkward family photos” and “awk example”. Once “awk” is submitted as a query, however, the search engine is likely to recognize the query as the “awk” programming language, and provide postsubmit suggestions such as “awk example”, “awk tutorial”, “sed”, etc.
Many, if not all, of the known query generation, query expansion and query reformulation techniques define the problem in the context that the input search query is given. Therefore, these techniques are only useful for postsubmit assistance.
A typical approach in commercial search engines for presubmit assistance is to complete a user's prefix to save the user from typing the query in manually, and also to help the user phrase their query when they start typing but do not exactly know which query terms to use or how to spell them. The widely accepted solution for the presubmit is to suggest the most frequent queries that match the user's portion of the search query. For example, suppose a user types, as a portion of a search query, the word “chinese” into a search query entry area, the top suggestions are typically “chinese new year”, “chinese dictionary”, “chinese translation”, and “chinese zodiac”, which are, in this example, the queries with the highest marginal frequency that match the portion of the search query.